function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * 通过一个层次遍历的数组生成一棵二叉树
 * @param {any[]} array
 * @return {TreeNode}
 */
function getTreeFromLayerOrderArray(array) {
  let n = array.length;
  if (!n) return null;
  let index = 0;
  let root = new TreeNode(array[index++]);
  let queue = [root];
  while (index < n) {
    let top = queue.shift();
    let v = array[index++];
    top.left = v == null ? null : new TreeNode(v);
    if (index < n) {
      let v = array[index++];
      top.right = v == null ? null : new TreeNode(v);
    }
    if (top.left) queue.push(top.left);
    if (top.right) queue.push(top.right);
  }
  return root;
}

/**
 * 层序遍历一棵二叉树 生成一个数组
 * @param {TreeNode} root
 * @return {any[]}
 */
function getLayerOrderArrayFromTree(root) {
  let res = [];
  let que = [root];
  while (que.length) {
    let len = que.length;
    for (let i = 0; i < len; i++) {
      let cur = que.shift();
      if (cur) {
        res.push(cur.val);
        que.push(cur.left, cur.right);
      } else {
        res.push(null);
      }
    }
  }
  while (res.length > 1 && res[res.length - 1] == null) res.pop(); // 删掉结尾的 null
  return res;
}


module.exports = {TreeNode, getTreeFromLayerOrderArray, getLayerOrderArrayFromTree};